package com.leetcode.根据算法进行分类.滑动窗口相关;

import java.util.HashMap;

/**
 * @author: ZhouBert
 * @date: 2021/2/5
 * @description: 3. 无重复字符的最长子串
 * https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/
 */
public class B_3_无重复字符的最长子串 {

	public static void main(String[] args) {
		B_3_无重复字符的最长子串 action = new B_3_无重复字符的最长子串();
		test1(action);
		test2(action);
		test3(action);
		test4(action);
	}

	public static void test1(B_3_无重复字符的最长子串 action ){
		String s = "pwwkew";
		//3
		System.out.println(action.lengthOfLongestSubstring(s));
	}

	public static void test2(B_3_无重复字符的最长子串 action ){
		String s = "anviaj";
		//5
		System.out.println(action.lengthOfLongestSubstring(s));
	}

	public static void test3(B_3_无重复字符的最长子串 action ){
		String s = "bbbbb";
		//1
		System.out.println(action.lengthOfLongestSubstring(s));
	}

	public static void test4(B_3_无重复字符的最长子串 action ){
		String s = "abcabcbb";
		//3
		System.out.println(action.lengthOfLongestSubstring(s));
	}


	public int lengthOfLongestSubstring(String s) {
		int res = 0;
		int len = s.length();
		if (len < 2) {
			return len;
		}
		//由于 英文字母、数字、符号和空格组成 + 无重复 -> 使用 hashMap( char-index)
		HashMap<Character, Integer> map = new HashMap<>();
		int begin = 0, end = 1;
		int index = 0;
		char[] chars = s.toCharArray();
		map.put(chars[0], 0);
		while (end < len) {
			while (end < len && (!map.containsKey(chars[end]) || map.get(chars[end]) < begin)) {
				//如果 都是不重复的元素
				map.put(chars[end], end++);
			}

			//此时 end 的位置重复了
			res = Math.max(res, end - begin);
			if (end == len) {
				break;
			}

			//拿到位置并更新
			index = map.get(chars[end]);
			begin = index + 1;
			end = Math.max(begin+1, end);
			//把 begin 的位置加入
			map.put(chars[begin], begin);
		}
		return res;

	}
}
